//
//  ShortestPalindrome.swift
//  LeetCodeSummary
//
//  Created by 彭西西 on 2020/8/29.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  214. 最短回文串

import UIKit

/*
 214. 最短回文串
 
 给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

 示例 1:

 输入: "aacecaaa"
 输出: "aaacecaaa"
 示例 2:

 输入: "abcd"
 输出: "dcbabcd"
 */

class ShortestPalindrome: NSObject {
    
    //暴力解法  官方最后两个用例超时  "aaaa.......aaaaa" 40002个a 中间夹了一个cd
    func shortestPalindrome(_ s: String) -> String {
        
        guard s.count > 1 else {
            return s
        }
        guard self.isPalindrome(s, 0, s.count-1) == false else{
            return s
        }
        
        //假设往前面增加 i 个字符可以满足要求 找出此时的回文中心（p），然后判断左边(s[0..p-1])和右边(s[p+1...n-p-i])是否构成回文串，构成的话就可以得到结果
        
        let arr = Array(s)
        
        var targetI = Int(INT32_MAX)
        
        for i in 1 ... s.count {
            //先找出回文中心
            if (i + arr.count)%2 == 0{
                //偶数，回文中心是2个字符串。
                let p1 = (i + arr.count)/2 - i - 1
                let p2 = p1 + 1
                
                if arr[p1] == arr[p2] {
                    if self.isPalindrome(s, 0, s.count-1-i){
                        //余下部分是回文串，此时已经找到
                        targetI = i
                        break
                    }else{
                        continue
                    }
                }else{
                    //不符合回文中心要求
                    continue
                }
                
            }else{
                //奇数，回文中心是1个字符串
                let p = (i + arr.count)/2 - i
                if p == 0{
                    targetI = i
                    break
                }
                if self.isPalindrome(s, 0, s.count-1-i){
                    //余下部分是回文串，此时已经找到
                    targetI = i
                    break
                }else{
                    continue
                }
            }
        }
        
        if targetI != Int(INT32_MAX) {
            //在字符串前面加上 i 个字符就可以满足要求，直接去后面 i 个字符进行倒置加到原始字符串前面即可得出结果
            var resultStr = [String]()
            for i in 0 ..< targetI {
                resultStr.append(String(arr[arr.count-1-i]))
            }
            
            let string = "\(resultStr.joined(separator: "")+s)"
            return string
        }
        
        return ""
    }
    
    //判断字符串的某个索引区间内是否是回文串
    func isPalindrome(_ string: String, _ left: Int, _ right: Int) -> Bool{

        let array = Array(string)
        let len = right - left + 1
        
        for i in 0 ..< len/2 {
            if array[left+i] != array[right-i] {
                return false
            }
        }
        return true
    }
    
    
    func isPalindrome2(_ string: String) -> Bool{
        return string == String(string.reversed())
    }
    
    
    
    //KMP解法
    /*
         public String shortestPalindrome(String s) {
             int n = s.length();
             int[] fail = new int[n];
             Arrays.fill(fail, -1);
             for (int i = 1; i < n; ++i) {
                 int j = fail[i - 1];
                 while (j != -1 && s.charAt(j + 1) != s.charAt(i)) {
                     j = fail[j];
                 }
                 if (s.charAt(j + 1) == s.charAt(i)) {
                     fail[i] = j + 1;
                 }
             }
             int best = -1;
             for (int i = n - 1; i >= 0; --i) {
                 while (best != -1 && s.charAt(best + 1) != s.charAt(i)) {
                     best = fail[best];
                 }
                 if (s.charAt(best + 1) == s.charAt(i)) {
                     ++best;
                 }
             }
             String add = (best == n - 1 ? "" : s.substring(best + 1));
             StringBuffer ans = new StringBuffer(add).reverse();
             ans.append(s);
             return ans.toString();
         }

     */
    func shortestPalindrome2(_ s: String) -> String {
        guard s.count > 1 else {
            return s
        }
        let sArr = Array(s)
        let n = s.count
        var fail = [Int](repeating: -1, count: n)
        
        for i in 1 ..< n{
            var j = fail[i-1]
            while j != -1 && sArr[j+1] != sArr[i] {
                j = fail[j]
            }
            if sArr[j+1] == sArr[i] {
                fail[i] = j + 1
            }
        }
        var best = -1
        for i in (0 ... n-1).reversed() {
            while best != -1 && sArr[best + 1] != sArr[i] {
                best = fail[best]
            }
            if sArr[best+1] == sArr[i] {
                best += 1
            }
        }
        
        let index: String.Index = s.index(s.startIndex, offsetBy: best+1)
        let add = best == n-1 ? "" : String(s[index ..< s.endIndex])    //等价于 subStringToIndex
        var ans = String(add.reversed())
        ans.append(s)
        
        return ans
    }
}
